#include<stdio.h>
#include<math.h>

int number[210][5];
int select[4][5];
int array[4][5];
int count;
int selecount;
int larray[2][200];
int lcount [2];

int main()
{
    int i,k,flag,cc=0,i1,i4;
    printf("There are magic squares with invertable primes as follow:\n");
    for (i=1001;i<9999;i+=2){
        k=i/1000;
        if(k%2!=0&&k!=5&&num(i)){
            number[count][0]=i;
            process(count++);
            if(number[count-1][2]%2!=0&&
               number[count-1][3]%2!=0&&
               number[count-1][2]!=5&&
               number[count-1][3]!=5)
               select[selecount++]=count-1;
        }
        
    }
larray[0][lcount[0]++]=number[0][0]/100;
larray[1][lcount[1]++]=number[0][0]/10;
for(i=1;i<count;i++){
    if(larray[0][lcount[0]-1]!=number[i][0]/100)
    larray[0][lcount[0]++]=number[i][0]/100;
    if(larray[1][lcount[1]-1]!=number[i][0]/10)
    larray[1][lcount[1]++]=number[i][0]/10;
}
for (i1=0;i1<selecount;i1++){
    array[0][0]=select[i1];
    copy_num(0);
    for(array[1][0]=0;array[1][0]<count;array[1][0]++){
        copy_num(1);
if(!comp_num(2))
continue;
for (array[2][0]=0;array[2][0]<count;array[2][0]++){
    copy_num(2);
    if(!comp_num(3))
    continue;
for(flag=1,i=1;flag&&i<=4;i++)
if(flag&&find2())
{
    printf("No.%d\n",++cc);p_array();
}

}
    }
}

}
num(int number)
{
    int j;
    if(! ok(number))return(0);
    for(j=0;number>0;number/10)
    j=j*10+number%10;
    if(!ok(j))return (0);
    return(1);

}
ok (int number)
{
    int i,j;
    if(number%2==0)return (0);
    j=sqrt((double)number)+1;
    for (i=3;i<=j;i+=2)
    if(number%i==0)return (0);
    return (1);

}
process (int i)
{
    int j,num;
    num=number[i][0];
    for(j=4;j>=1;j--,num/=10)
    number[i][j]=num%10;

}
copy_num(int i)
{
    int j;
    for (j=1;j<+4;j++)
    array[i][j]=number[array[i][0]][j];

}
comp_num(int n)
{
    static int ii;
    static int jj;
    int i,num,k;
    int *pcount;
    int *p=NULL;
    switch(n){
        case 2:pcount=&lcount[0];p=&ii;break;
        case 3:pcount=&lcount[1];p=&jj;break;
        default: return(0);
        
        }

        for(i=1;i<=4;i++){
            for(num=0,k=0;k<n;k++)
            num=num*10+array[k][i];
            if(num<=larray[n-2][*p])
            for(;*p>=0&&num<larray[n-2][*p];(*p)++);
            if(*p<0||*p>=*pcount){
                *p=0;return(0);
            }
        if(num!=larray[n-2][*p])
        return (0);

        
        }
return(1);

}
find1(int i)
{
    int num,j;
    for (num=0,j=0;j<4;j++)num=num*10+array[j][i];
    return(find0(num));
}
find2(void)
{
    static int j;
    if(num<=number[j][0])for(;j>=0&&num<number[j][0];j--);
    else for(;j<count&&num>number[j][0];j++);
    if(j<0||j>=count){j=0;return(0);}
    if(num==number[j][0])return(1);
    else return(0);


}
p_array(void)
{
    int i,j;
    for (i=0;i<4;j++){
    printf("%6d",array[i][j]);
    printf("\n");
    }
}
